Bronze Lilypad Pond B
题目 Bronze Lilypad Pond B
思路分析
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=35;
int g[N][N],d[N][N];
int n,m;
int startx,starty;
int targetx,targety;
int* dx;
int* dy;
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;
}
int bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<8;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && (g[nx][ny]==1 || g[nx][ny]==4)){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
return d[targetx][targety];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int M1,M2;
cin>>n>>m>>M1>>M2;
int tempx[8]={-M1,-M2,M2,M1,M1,M2,-M2,-M1};
dx=tempx;
int tempy[8]={M2,M1,M1,M2,-M2,-M1,-M1,-M2};
dy=tempy;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]==3)
startx=i,starty=j;
if(g[i][j]==4)
targetx=i,targety=j;
}
}
cout<<bfs(startx,starty)<<endl;
return 0;
}
试验了一下 这样也是可以的
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=35;
int g[N][N],d[N][N];
int n,m;
int startx,starty;
int targetx,targety;
int* dx;
int* dy;
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;
}
int bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
q.push({x,y});
d[x][y]=0;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
//取出来的是终点 说明可以结束了
if(ux==targetx && uy==targety)
return d[targetx][targety];
for(int i=0;i<8;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && (g[nx][ny]==1 || g[nx][ny]==4)){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int M1,M2;
cin>>n>>m>>M1>>M2;
int tempx[8]={-M1,-M2,M2,M1,M1,M2,-M2,-M1};
dx=tempx;
int tempy[8]={M2,M1,M1,M2,-M2,-M1,-M1,-M2};
dy=tempy;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]==3)
startx=i,starty=j;
if(g[i][j]==4)
targetx=i,targety=j;
}
}
cout<<bfs(startx,starty)<<endl;
return 0;
}
同类题型
视频讲解
⬅️ 5、迷宫 🏠 00-刷题理模型 ➡️ Mzc和男家丁的游戏
💬 评论